Flash memory devices are electronic non-volatile computer storage media that allow accessing or reading stored data, writing new data and erasing stored data. In recent years, due to the overwhelming advantage of large memory size and high rewriting speed, flash memory has played a major role in the non-volatile memory market. Flash memories are used in a variety of applications, for example in USB drives for personal information storage, or embedded in credit cards or gift cards to enable financial payments or transactions. Generally flash memory devices are used especially for application in which the data is rarely changed but read many times, since they can be read faster than they can be written.
Typically two types of technology are used to manufacture flash memory: NAND and NOR. NAND flash memory is generally characterized by having long rows of bits and they are written a row at a time. To change even a single bit the entire row must be read to a buffer, amended and then written back. In contrast the NOR flash memory technology allows writing the value ‘0’ (zero) to any physical bit address in the storage device, and setting the values to ‘1’ (one) when erasing a sector which includes a plurality of bits (e.g. a row). Generally a flash memory is initialized with the value of ‘1’ (one) in all the bits, so that an application can easily write initial data by changing ‘1’ bits to zeros. Changing zero bits back to ones is a slower and more complex process typically requiring backing up the current information of the entire sector to a work memory, correcting the desired bits, erasing the sector in the flash memory by initializing it to ones and changing selected bits to zero based on the modified content of the work memory. Thus erasing or updating data (i.e. changing zero bits back to one) in a flash memory is a relatively expensive operation and affects relatively large memory areas (Sectors). There is no way to erase smaller entities, like separate bits, bytes or words.
A possible solution to make it easier to “rewrite” data in the flash memory is to substitute another physical location for the same logical address. Thus, to rewrite a value at a given logical address, the following process is performed:                1. Find the physical location currently associated with the required address        2. Find and associate the next physical available location for the given address.        3. Write the updated value to the new location.        
Typically a flash memory may include multiple sectors that are divided into multiple blocks of a preselected size. Any address can be presented as a sector number and a block offset in the sector. A memory management unit associates between physical and virtual blocks, and each virtual address is translated to a physical address by:(physical address)=(the address of the associated physical sector)+(block offset in the sector).
For each physical block, the flash memory stores a number of flags denoting whether the block is empty (e.g. unused), associated (e.g. is being used) or expired (e.g. was used and the data was cancelled or transferred to a new block). If the block is associated, then the number of the virtual associated block is also stored in the flash memory.
When the content of the memory at a certain location is updated, the following is performed:                1. The updated content of the entire physical block associated with the virtual block at the location is copied to another physical block        2. The block association mapping is updated accordingly, namely, the previous physical block is marked as unassociated or expired and the new block is marked as associated to the associated virtual block.        
Accordingly, to find the physical block currently associated with a given virtual block, the flash memory manager unit has to scan the entire memory array looking for the physical block currently marked as associated with the address of the current virtual block. In practice, this is a time consuming procedure that may be performed once upon initialization of the flash memory device for all virtual block addresses. The mapping information is then stored in a RAM in a form of a large look-up table, comprising an entry for each virtual block. When using a large flash memory the look up table can be large and consume a sizable amount of RAM.